점근 표기법

알고리즘의 시간 복잡도 설명에 사용하는 표기법. $f(n) = O(n^2)$ 꼴로 쓴다.

On notation

$\Theta(g(n))$ is a set:

Because $\Theta(g(n))$ is a set, we could write "$f(n) \in \Theta(g(n))$" to indicate that $f(n)$ is a member of $\Theta(g(n))$. Instead, we will usually write "$f(n)=\Theta(g(n))$" to express the same notion.¹

Minor abusing:

Since any constant is a degree-0 polynomial, we can express any constant function as $\Theta(n^0)$, or $\Theta(1)$. This latter notation is a minor abuse, however, becuase the expression doesn not indicate what variable is tending to infinity. We shall often use the notation $\Theta(1)$ to mean either a constant or a constant function with respect to some variable.

(The real problem is that our ordinary notation for functions does not distinguish functions from values. in Lambda calculus, the parameters to a function are clealy specified: the function $n^2$ could be written as $\lambda n.n^2$, or even $\lambda r.r^2$. Adopting a more rigorous notation, howevery, would complicate algebraic manipulations, and so we choose to tolerate the abuse.)¹

$\Theta$-notation (Big Theta notation)

정의:¹

For a given function $g(n), we denote by$\Theta(g(n))$ the set of functions

$\Theta(g(n))$ = { $f(n)$ such that there exist positive constants $c_1$, $c_2$, and $n_0$ such that $0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n)$ for all $n \geq n_0$ .

설명:¹

A function $f(n)$ belongs to the set $\Theta(g(n))$ if there exist positive constants $c_1$ and $c_2$ such that it can be “sandwiched” between $c_1 g(n)$ and $c_2 g(n)$, for sufficiently large $n$. … In other words, for all $n \geq n_0$, the function $f(n)$ is equal to $g(n)$ to within a constant factor. We say that $g(n)$ is an asymptotically tight bound for $f(n)$.

$\Omega$-notation (Big Omega notation)

O-notation (Big O notation)

Footnotes

1. Chapter 3, Introduction to algorithms ↩ ↩² ↩³ ↩⁴